package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/10/18 下午4:22
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


import org.junit.Test;

import java.util.Scanner;

/**
题目描述
 一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1，3，5个字符就构成子串" cad" ,现给定两个字符串，求它们的最长共公子串。

 输入
 第一行两个字符串用空格分开。两个串的长度均小于2000 。
 输出
 最长子串的长度。


 样例输入
 abccd aecd
 样例输出
 3
*/

// 分析

// dp经典问题

// 1. 可以划分子问题求解
// 2. 满足最优子结构性质
// 3. 保存结果，避免重复计算

public class MaxSequence {


    public static int getSubStrLen(String a, String b){
        int aLength = a.length(), bLength = b.length();
        int[][] count = new int[aLength+1][bLength+1]; // count[i][j] 存储a中前i个序列和b中前j个序列最长公共字串的长度
        // for(int i = 0; i <= bLength; ++i)count[0][i] = 0;
        // for(int j = 0; j <= bLength; ++j)count[j][0] = 0;
        // 自动初始化为0, for循环省略
        for(int m = 1; m <= aLength; ++m){
            for(int k = 1; k <= bLength; ++k){
                if(a.charAt(m-1) == b.charAt(k-1)){
                    count[m][k] = count[m-1][k-1] + 1;
                }  else {
                    count[m][k] = Math.max(count[m-1][k], count[m][k-1]);
                }
            }
        }
        return count[aLength][bLength];
    }

    public static void main(String[] args) {
        /*System.out.println(getSubStrLen("abccd", "aecd") == 3);
        System.out.println(getSubStrLen("abccd", "abccd") == 5);
        System.out.println(getSubStrLen("", "aecd") == 0);
        System.out.println(getSubStrLen("adf", "") == 0);
        System.out.println(getSubStrLen("", "") == 0); // 都是空串，返回0*/


        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(getSubStrLen(a, b));
    }
}
